import java.util.Arrays;

/**
 * @author WangTianyi
 * @create 2021-12-03 20:31
 */
public class InsertionSort {

    public static void main(String[] args) {
        double[] array1 = new double[]{45, 34, 78, 12, 34, 32, 29, 64};
        double[] array2 = new double[]{45, 34, 78, 12, 34, 32, 29, 64};
        double[] array3 = new double[]{45, 34, 78, 12, 34, 32, 29, 64};
        insertionSort(array1);
        System.out.println(Arrays.toString(array1));
        insertionSortPro(array2);
        System.out.println(Arrays.toString(array2));
        insertionSortProMax(array3);
        System.out.println(Arrays.toString(array3));
    }



    //每一次都交换二者位置，效率相对很低
    public static void insertionSort(double[] array) {
        for (int i = 1; i < array.length; i++) {
            for (int j = i - 1; j >= 0; j--) {
                if (array[j + 1] < array[j]) swap(array, j, j + 1);
                else break;
            }
        }
    }

    //课本上的写法，即不每次交换位置，只是后移，最后把将要插入有序序列中的值（temp）插入到插入位上
    public static void insertionSortPro(double[] array) {
        for (int i = 1; i < array.length; i++) {
            double temp = array[i];
            int j;
            for (j = i - 1; j >= 0; j--) {
                if (temp < array[j]) array[j + 1] = array[j];
                else break;
            }
            array[j + 1] = temp;
        }
    }

    //通过二分查找实现的二分插入排序，时间效率理论上高于直接插入排序
    public static void insertionSortProMax(double[] array) {
        for (int i = 1; i < array.length; i++) {
            double temp = array[i];
            int low = 0;
            int high = i - 1;
            int mid = 0;
            while (low <= high) {
                mid = (low + high) / 2;
                if (array[mid] > temp) {//若mid位置的值大于temp，则插入位置在mid的左侧，即[low,mid-1]中
                    high = mid - 1;
                } else {//否则，则插入位置在mid的右侧，即[mdi+1,high]中
                    low = mid + 1;
                }
            }
            for (int j = i; j > low; j--) {//把low和low之后的元素统统后移一个位置
                array[j] = array[j-1];
            }
            array[low] = temp;//low所在位置即为插入位
        }
    }

    //待排序的数组下标区间通过形参传入，而不再是给整个数组排序，可复用性更强
    public static <T extends Comparable> void insertionSortProMaxPlus(T[] array, int left, int right) {
        for (int i = left+1; i <= right; i++) {
            T temp = array[i];
            int low = left;
            int high = i - 1;
            int mid = 0;
            while (low <= high) {
                mid = (low + high) / 2;
                if (array[mid].compareTo(temp)>0) {//若mid位置的值大于temp，则插入位置在mid的左侧，即[low,mid-1]中
                    high = mid - 1;
                } else {//否则，则插入位置在mid的右侧，即[mdi+1,high]中
                    low = mid + 1;
                }
            }
            for (int j = i; j > low; j--) {//把low和low之后的元素统统后移一个位置
                array[j] = array[j-1];
            }
            array[low] = temp;//low所在位置即为插入位
        }
    }

    public static void swap(double[] array, int indexi, int indexj){
        double temp = array[indexi];
        array[indexi] = array[indexj];
        array[indexj] = temp;
    }

}
